package leetcode.code1993;

import java.util.ArrayList;
import java.util.List;

import leetcode.helper.H;

public class LockingTree {

	int n;
	int[] locked;
	List<Integer>[] children;
	int[] parent;

	public LockingTree(int[] parent) {
		n = parent.length;
		locked = new int[n];
		children = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			children[i] = new ArrayList<>();
		}
		for (int i = 0; i < parent.length; i++) {
			if (parent[i] != -1)
				children[parent[i]].add(i);
		}
		this.parent = parent;
	}

	public boolean lock(int num, int user) {
		if (locked[num] == 0) {
			locked[num] = user;
			return true;
		}
		return false;
	}

	public boolean unlock(int num, int user) {
		if (locked[num] == user) {
			locked[num] = 0;
			return true;
		}
		return false;
	}

	public boolean upgrade(int num, int user) {
		// 指定节点当前状态为未上锁 &&
		if (locked[num] == 0 && this.checkUnlock(num) && this.checkLock(num)) {
			// 指定用户给指定节点 上锁
			locked[num] = user;
			// 并且将该节点的所有子孙节点 解锁
			this.unlock(num);
			return true;
		}
		return false;
	}

	private void unlock(int num) {
		List<Integer> cur = children[num];
		for (int i = 0; i < cur.size(); i++) {
			int child = cur.get(i);
			if (this.locked[child] != 0) {
				this.locked[child] = 0;
			}
			this.unlock(child);
		}
	}

	// 指定节点至少有一个上锁状态的子孙节点（可以是 任意 用户上锁的）
	private boolean checkLock(int num) {
		List<Integer> cur = children[num];
		for (int i = 0; i < cur.size(); i++) {
			int child = cur.get(i);
			if (this.locked[child] != 0) {
				return true;
			}
			if (this.checkLock(child)) {
				return true;
			}
		}
		return false;
	}

	private boolean checkUnlock(int num) {
		while (parent[num] != -1 && this.locked[parent[num]] == 0) {
			num = this.parent[num];
		}
		return parent[num] == -1;
	}
	
	public static void main(String[] args) {
		LockingTree lockingTree = new LockingTree(H.str2array3("[-1,0,0,1,1,2,2]"));
		lockingTree.lock(2, 2);    // 返回 true ，因为节点 2 未上锁。
		                           // 节点 2 被用户 2 上锁。
		lockingTree.unlock(2, 3);  // 返回 false ，因为用户 3 无法解锁被用户 2 上锁的节点。
		lockingTree.unlock(2, 2);  // 返回 true ，因为节点 2 之前被用户 2 上锁。
		                           // 节点 2 现在变为未上锁状态。
		lockingTree.lock(4, 5);    // 返回 true ，因为节点 4 未上锁。
		                           // 节点 4 被用户 5 上锁。
		lockingTree.upgrade(0, 1); // 返回 true ，因为节点 0 未上锁且至少有一个被上锁的子孙节点（节点 4）。
		                           // 节点 0 被用户 1 上锁，节点 4 变为未上锁。
		lockingTree.lock(0, 1);    // 返回 false ，因为节点 0 已经被上锁

	
	}

}
